#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
using namespace std;
// 降序
class Sort
{
public:
    //直接插入排序
	static void InsertSort(vector<int>& nums)
	{
		int n = nums.size();
		for (int i = 0; i < n - 1; i++)
		{
			int end = i;
			int prev = nums[i + 1];
			while (end >= 0)
			{
				if (prev > nums[end])
				{
					swap(nums[end + 1], nums[end--]);
				}
				else
					break;
			}
			nums[end + 1] = prev;
		}
	}
    //shell排序
	static void ShellSort(vector<int>& nums)
	{
		int n = nums.size();
		int gap = n;
		while (gap >= 1)
		{
			gap /= 2;
			for (int i = 0; i < n - gap; i++)
			{
				int end = i;
				int last = nums[end + gap];
				while (end >= 0)
				{
					if (last > nums[end])
					{
						swap(nums[end + gap], nums[end]);
						end -= gap;
					}
					else
						break;
				}
				nums[end + gap] = last;
			}
		}
	}
    //冒泡排序
	static void BubbleSort(vector<int>& nums)
	{
		int n = nums.size();
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n - i - 1; j++)
			{
				if (nums[j] < nums[j + 1])
				{
					swap(nums[j], nums[j + 1]);
				}
			}
		}
	}
    //快排
	static void QuickSort(vector<int>& nums)
	{
		srand(time(nullptr));
		int n = nums.size();
		int left = 0;
		int right = n - 1;
		_QuickSort(nums, left, right);
	}
	static void QuickSortNonR(vector<int>& nums)
	{
		srand(time(nullptr));
		int left = 0;
		int right = nums.size() - 1;
		_QuickSortNonR(nums, left, right);
	}
    //归并
	static void MergeSort(vector<int>& nums)
	{
		int n = nums.size();
		int left = 0;
		int right = n - 1;
		_MergeSort(nums, left, right);
	}
	static void MergeSortNonR(vector<int>& nums)
	{
		int n = nums.size();
		int left = 0;
		int right = n - 1;
		_MergeSoreNonR(nums, left, right);
	}
    //计数排序
	static void CountSort(vector<int>& nums)
	{
		int n = nums.size();
		map<int, int, greater<int>> cnums;
		for (auto& e : nums)
			cnums[e]++;
		int i = 0;
		for (auto& e : cnums)
		{
			while (e.second--)
				nums[i++] = e.first;
		}
	}
    //选择排序
	static void SelectSort(vector<int>& nums)
	{
		int n = nums.size();
		int end = n - 1;
		int begin = 0;
		int max = 0, min = 0;
		while (begin < end)
		{
			max = begin;
			min = begin;
			for (int i = begin; i <= end; i++)
			{
				if (nums[i] < nums[min])
					min = i;
				else if (nums[i] > nums[max])
					max = i;
			}
			swap(nums[min], nums[begin++]);
			//如果最大值和最小值是首元素，则最大值的下标与最小值的下标相等，因为前一个交换导致最大值
			//下表发生位移
			if (max == begin)
				max = min;
			swap(nums[max], nums[end--]);
		}
	}
    //堆排
	static void HeapSort(vector<int>& nums)
	{
		int n = nums.size();
		for (int i = (n - 1 -1) / 2; i >= 0; i--)
		{
			_AdjustDown(nums, i, n);//建堆
		}
		int end = n - 1;
		while (end >= 1)
		{
			swap(nums[end], nums[0]);
			_AdjustDown(nums, 0, end);
			end--;
		}
	}
    //桶排序
	static void BucketSort(vector<int>& nums)
	{
		int n = nums.size();
		int min = nums[0];
		int max = nums[0];
		for (int i = 0; i < n; i++)
		{
			if (nums[i] > max) max = nums[i];
			if (nums[i] < min) min = nums[i];
		}
		int size = (max - min) / n + 1;
		int cut = (max - min) / size + 1;
		vector<vector<int>> bock(cut);
		for (int i = 0; i < n; i++)
		{
			int idx = (nums[i] - min) / size;
			bock[idx].push_back(nums[i]);
		}
		for (int i = 0; i < cut; i++)
			ShellSort(bock[i]);
		int index = 0;
		for (int i = 0; i < cut; i++)
		{
			for (int j = 0; j < bock[i].size(); j++)
				nums[index] = bock[i][j];
		}
	}
private:
    //快排递归
	static void _QuickSort(vector<int>& nums, int left, int right)
	{
		if (left >= right) return;
		int prev = left - 1;
		int last = right + 1;
		int cur = left;//当前值
		int mid = nums[rand() % (right - left + 1) + left];// 寻找中间值
		while (cur < last)
		{
			if (nums[cur] > mid) swap(nums[cur++], nums[++prev]);
			else if (nums[cur] == mid) cur++;
			else if (nums[cur] < mid) swap(nums[cur], nums[--last]);
		}
		_QuickSort(nums, left, prev);
		_QuickSort(nums, last, right);
	}
    //非递归
	static void _QuickSortNonR(vector<int>& nums, int left, int right)
	{
		stack<int> st;
		st.push(left);
		st.push(right);
		while (st.size() > 0)
		{
			int end = st.top();
			st.pop();
			int begin = st.top();
			st.pop();
			int prev = begin - 1;
			int last = end + 1;
			int cur = begin;//当前值
			int mid = nums[rand() % (end - begin + 1) + begin];// 寻找中间值
			while (cur < last)
			{
				if (nums[cur] > mid) swap(nums[cur++], nums[++prev]);
				else if (nums[cur] == mid) cur++;
				else if (nums[cur] < mid) swap(nums[cur], nums[--last]);
			}
			if (begin < prev)
			{
				st.push(begin);
				st.push(prev);
			}
			if (last < end)
			{
				st.push(last);
				st.push(end);
			}
		}
	}
    //递归归并
	static void _MergeSort(vector<int>& nums, int left, int right)
	{
		if (left >= right) return;
		//int mid = (right + left) / 2;
		int mid = left + (right - left) / 2;
		_MergeSort(nums, left, mid);
		_MergeSort(nums, mid + 1, right);
		int prev1 = left, last1 = mid;
		int prev2 = mid + 1, last2 = right;
		vector<int> _nums(right + 1);
		int cur = left;
		while (prev1 <= last1 && prev2 <= last2)
			_nums[cur++] = nums[prev1] < nums[prev2] ? nums[prev2++] : nums[prev1++];
		while (prev1 <= last1)
			_nums[cur++] = nums[prev1++];
		while (prev2 <= last2)
			_nums[cur++] = nums[prev2++];
		for (cur = left; cur <= right; cur++)
			nums[cur] = _nums[cur];
	}
    //非递归
	static void _MergeSoreNonR(vector<int>& nums, int left, int right)
	{
		int gap = 1;
		int i = left;
		vector<int> _nums(right + 1);
		while (gap <= right)
		{
			for (i = 0; i <= right; i += 2 * gap)
			{
				//[i,I+gap-1]  [i+gap,2*gap-1]
				int prev1 = i, last1 = i + gap - 1;
				int prev2 = i + gap, last2 = i + 2 * gap - 1;
				//printf(" %d", end2);
				if (last1 > right) last1 = right;
				if (prev2 > right)
				{
					prev2 = right + 1;
					last2 = right;
				}
				if (last2 > right) last2 = right;
				int cur = prev1;
				while (prev1 <= last1 && prev2 <= last2)
					_nums[cur++] = nums[prev1] < nums[prev2] ? nums[prev2++] : nums[prev1++];
				while (prev1 <= last1)
					_nums[cur++] = nums[prev1++];
				while (prev2 <= last2)
					_nums[cur++] = nums[prev2++];
			}
			for (i = 0; i <= right; i++)
				nums[i] = _nums[i];
			gap *= 2;
		}
	}
	static void _AdjustDown(vector<int>& nums, int parent, int n)
	{
		int child = parent * 2 + 1;
		while (child < n)
		{
			if (child + 1 < n && nums[child] < nums[child + 1])
				child += 1;
			if (nums[parent] < nums[child])
			{
				swap(nums[parent], nums[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else break;
		}
	}
};